Open problems

This page lists a few open problems I'm interested in. It should be seen as a personal page I don't mind making public, because I will not take the time here to explain the full details of everything I mention. However, I have sometimes provided a few references I know about on the subject, which you can access by clicking the corresponding "bib" link. For further information, my publications may also help. If you have ideas, don't hesitate to get in touch: I'm always up for teamwork, and I'd really like to have more coauthors. Updated stuff will be in red and/or brought back on top of the list.

I used to maintain a summary of all open problems from ISGCI, but they now do it themselves, so I've discarded it.

• Sorting by prefix double-cut-and-joins:
  • determine the complexity of the problem in the unsigned case (the signed case is easy); the journal version of our SPIRE 2022 paper features a polynomial-time algorithm for that problem
  • if hard: can we do better than our 3/2-approximation? (see our SPIRE 2022 paper)
• Sorting by prefix block-interchanges:
  • determine the complexity of the problem;
  • if hard: can we do better than my 2-approximation? (I have a 4/3-approximation for simple permutations, see this preprint);
• Minimum common supergraphs of partially labelled graphs: (there are some results in my Ph. D. thesis)
  • complexity of the problem on two trees (it's hard on three or more, see my paper with Sicco Verwer);
  • other tractable cases than restricted graphs?
• Maximum common subgraph: given a graph and a tree, both of which are partially vertex-labelled, find their maximum common subgraph. The problem is NP-hard, but how fast can we solve it?
• "Warmuth's conjecture": does every concept class of finite VC dimension d have a compression scheme of size d?
• Sorting by transpositions: bib
  • determine the transposition diameter;
• Burnt pancake flipping: my paper with Josef Cibulka features a new tight lower bound on the prefix signed reversal distance, and we are able to sort simple permutations in polynomial time; future work could include:
  • tightening the lower bound for arbitrary permutations;
  • designing improved approximation algorithms based on that lower bound;
  • and of course, settling the complexity of the problem; note that the unburnt variant is now known to be NP-hard
• Path-dependent shortest path problems: given an edge-weighted digraph, find a least-cost path from vertex s to vertex t. The catch: path cost depends not only on edge weights, but also on which path you've taken.
  • the general problem is NP-hard; in which case can we prove polynomial time solvability?
  • the "suffix-k" variant (path cost can be altered by at most k edges) can be solved in O(|V|^k|E|) time; can we do better than that?
• Gift wrapping: currently researching the literature (if you can help me, please drop me a line! I don't even know if the name is accurate), but the problem I'm interested in is the following:
  • given a polyhedron and a sheet of paper, how can you wrap the polyhedron using as little paper as possible?
• Sorting by prefix transpositions: bib
  • determine the complexity of the problem;
  • determine the prefix transposition diameter (lies between 3n/4 and n-1);
• Pancake flipping:
  • can the current best approximation ratio (2) by Fischer and Ginzinger be outperformed?
• Edit distances in general: my SIDMA 2013 paper introduces a simple and generic way to obtain lower bounds on edit distances on permutations. It spawns a number of interesting questions, for instance:
  • can we generalise the model to other structures (e.g. signed permutations, strings, ...)?
  • can we extend the model to derive upper bounds rather than lower bounds?
• Universal graphs:
  • bounds for the number of edges in a universal graph for spanning trees?
  • can we characterise "optimal" universal graphs?

Other problems that have been giving brilliant minds a hard time can be found through these links:

• The Open Problem Garden is a collection of open problems in mathematics and theoretical computer science
• The Open Problems Project focuses on computational geometry
• If you need money or are looking for something really serious, check out the Millenium Problems